package com.github.hgkmail.hello.leetcode101.design;

import java.util.*;

//插入、删除O(1) -> HashMap
//随机访问O(1) -> ArrayList
//RandomizedSet = HashMap + ArrayList（ArrayList只在尾部进行插入和删除）
public class LC380InsertDeleteGetRandomO1 {
    public static class RandomizedSet {
        private Map<Integer, Integer> index;
        private List<Integer> list;
        private Random random;

        public RandomizedSet() {
            //value, array index
            index = new HashMap<>();
            //只在尾部进行插入和删除
            list = new ArrayList<>();

            random = new Random();
        }

        public boolean insert(int val) {
            if (index.containsKey(val)) {
                return false;
            }
            int len=list.size();
            list.add(val); // append到列表尾部
            index.put(val, len); //存下标
            return true;
        }

        public boolean remove(int val) {
            if (!index.containsKey(val)) {
                return false;
            }
            int loc = index.get(val);
            int last = list.size()-1;
            int lastNum = list.get(last);
            //用last的元素代替loc的元素
            list.set(loc, list.get(last));
            index.put(lastNum, loc);
            //删除ArrayList最后一个元素，不用移动数组，符合O(1)
            list.remove(last);
            index.remove(val);

            return true;
        }

        public int getRandom() {
            int loc = random.nextInt(list.size()); //[0,size)
            return list.get(loc);
        }
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(0);
        randomizedSet.insert(1);
        randomizedSet.remove(0);
        randomizedSet.insert(2);
        randomizedSet.remove(1);
        System.out.println(randomizedSet.getRandom());
    }
}
